/**
 * [81] 搜索旋转排序数组 II
 *
 * @format
 * @lc app=leetcode.cn id=81 lang=javascript
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {boolean}
 */
var search = function (nums, target) {
    let [left, right, mid] = [0, nums.length - 1, 0]
    // let mid = Math.floor((left + right) / 2)
    // if (nums[mid] === target) return true
    let [A, B, C] = [true, true, true]
    let count = 0
    while (left <= right && count < nums.length / 2 + 1) {
        if (nums[mid] === target) return true
        // target 在 nums 左
        A = target >= nums[0]
        // mid 在 nums 左
        B = nums[mid] >= nums[0]
        if (nums[mid] == nums[0]) {
            let i = mid
            while (i > 0) {
                if (nums[i - 1] != nums[0]) B = false
                i--
            }
        }
        // mid 在 target 右
        C = nums[mid] > target
        if ((A && B && C) || (A && !B && !C) || (!A && !B && C)) {
            right = mid
            mid = Math.floor((left + right) / 2)
        } else {
            left = mid
            mid = Math.floor((left + right + 1) / 2)
        }
        count++
    }
    return false
}
// debugger
// const nums = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1]
// const target = 2
// const result = search(nums, target)
// console.log(result)
// @lc code=end
